﻿using System;
using System.Collections.Generic;
using System.Diagnostics;
using System.Linq;
using System.Runtime.Serialization;
using System.Security.Permissions;
using System.Text;
using System.Xml.Serialization;

namespace SolverTemplateLib
{
    /// <summary>
    /// The 'BackTracker' abstract class
    /// </summary>
    /// Make it serializable, so derived classes can be serialized
    [Serializable] 
    public abstract class BackTracker : ISerializable
    {
        public abstract bool IsCancelled();
        public abstract bool IsSolution();
        public abstract void ProcessSolution();
        public abstract void ProcessCandidate();
        public abstract List<BackTracker> Candidates();

        // The "Template method"
        public IEnumerable<BackTracker> Solve()
        {
            if (this.IsSolution())
            {
                this.ProcessSolution();
                yield return this;
            }

            List<BackTracker> C = Candidates();
            foreach (BackTracker c in C)
                if (this.IsCancelled())
                    yield break;
                else
                {
                    c.ProcessCandidate();
                    foreach (BackTracker s in c.Solve())
                    {
                        yield return s;
                    }
                }
        }

        // The ISerializable interface
        public virtual void GetObjectData(SerializationInfo info, StreamingContext context)
        {
        }
    }
    /// <summary>
    /// A 'BackTrackerTester' class
    /// </summary>
    class BackTrackerTester : BackTracker
    {
        private int _s;
        private int _v;
        public BackTrackerTester(int s, int v)
        {
            Debug.WriteLine("BackTrackerTester() [creator]: " + s.ToString() + ", " + v.ToString());
            _s = s;
            _v = v;
        }
        public override bool IsCancelled()
        {
            return false;
        }
        public override bool IsSolution()
        {
            bool result = ((_v % 2) == 1);
            Debug.WriteLine("IsSolution(" + _v.ToString() + ") = " + result.ToString());
            return result;
        }
        public override void ProcessCandidate()
        {
            Debug.WriteLine("ProcessCandidate() : " + _v.ToString());
        }
        public override void ProcessSolution()
        {
            Debug.WriteLine("ProcessSolution() : " + _v.ToString());
        }
        public override List<BackTracker> Candidates()
        {
            Debug.WriteLine("Candidates()");
            List<BackTracker> r = new List<BackTracker>();
            r.Add(new BackTrackerTester(_s + 1, 0));
            r.Add(new BackTrackerTester(_s + 1, 1));
            r.Add(new BackTrackerTester(_s + 1, 3));
            List<BackTracker> e = new List<BackTracker>();

            if (_s < 1)
                return r;
            else
                return e;
        }
    }
    class PermBackTracker : BackTracker
    {
        private List<int> _l;
        private String _state;

        public PermBackTracker()
        {
            _l = new List<int>();
            for (int i = 1; i < 5; i++)
                _l.Add(i);
            _state = "State: ";
            Debug.WriteLine("Created instance of: " + this.GetType());
        }

        public PermBackTracker(List<int> l, String state)
        {
            _l = l;
            _state = state;
        }
        public override bool IsCancelled()
        {
            return false;
        }
        public override bool IsSolution()
        {
            // any completed permutation is a solution
            return (_l.Count == 0);
        }
        public override void ProcessSolution()
        {
            Debug.WriteLine(_state);
        }
        public override void ProcessCandidate()
        {
            // empty
        }
        public override List<BackTracker> Candidates()
        {
            List<BackTracker> result = new List<BackTracker>();

            foreach (int i in _l)
            {
                List<int> l1 = new List<int>(_l);
                l1.Remove(i);
                result.Add(new PermBackTracker(l1, _state + i.ToString()));
            }
            return result;
        }
    }
}
